//图像渲染
class Solution {
    using PII = pair<int,int>;
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
 public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int n = image.size() , m = image[0].size();
        int srcColor = image[sr][sc];
        if(srcColor == color) return image;
        queue<PII> q;
        q.push({sr,sc});
        //bfs
        while(!q.empty())
        {

            PII p = q.front();
            image[p.first][p.second] = color;
            q.pop();
            for(size_t i = 0 ; i < 4 ; ++i)
            {
                int y = p.first + dy[i] , x = p.second + dx[i];
                if(y >= 0 && y < n && x >= 0 && x < m && image[y][x] == srcColor) q.push({y,x});
            }
        }
        return image;
    }
};

//岛屿数量
class Solution {
public:
    using PII = pair<int,int>;
    bool check[301][301];
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size() , m = grid[0].size();
        queue<PII> q;
        int ret = 0;
        for(int i = 0 ; i < n ; ++i)
        {
            for(int j = 0 ; j < m ; ++j)
            {
                if(check[i][j] == false && grid[i][j] == '1') 
                {
                    q.push({i,j});
                    ++ret;
                }
                while(!q.empty())
                {
                    auto p = q.front();
                    q.pop();
                    check[p.first][p.second] = true;
                    for(size_t i = 0 ; i < 4 ; ++i)
                    {
                        int y = p.first + dy[i] , x = p.second + dx[i];
                        if(y >= 0 && x >= 0 && y < n && x < m && check[y][x] == false && grid[y][x] == '1') 
                        {
                            check[y][x] = true;
                            q.push({y,x});
                        }
                    }
                }
            }
        }
        return ret;
    }
};

//岛屿的最大面积
class Solution {
public:
    bool check[51][51];
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    using PII = pair<int,int>;
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        queue<PII> q;
        int ret = 0;
        int m = grid.size() , n = grid[0].size();
        for(int i = 0 ; i < m ; ++i)
        {
            for(int j = 0 ; j < n ; ++j)
            {
                int count = 0;
                if(check[i][j] == false && grid[i][j] == 1)
                {
                    q.push({i,j});
                    check[i][j] = true;
                }
                while(!q.empty())
                {
                    auto [a,b] = q.front();
                    q.pop();
                    count++;
                    for(size_t k = 0 ; k < 4 ; ++k)
                    {
                        int y = a + dy[k] , x = b + dx[k];
                        if(x >= 0 && y >= 0 && x < n && y < m && check[y][x] == false && grid[y][x] == 1)
                        {
                            q.push({y,x});
                            check[y][x] = true;
                        }
                    }
                }
                ret = max(ret , count);
            }
        }
        return ret;
    }
};

//被围绕的区域
class Solution {
public:
    using PII = pair<int,int>;
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    int m,n;
    void bfs(vector<vector<char>>& board,int sr , int sc)
    {
        queue<PII> q;
        q.push({sr,sc});
        board[sr][sc] = '.';
        while(!q.empty())
        {
            auto [a,b] = q.front();
            q.pop();
            for(size_t i = 0 ; i < 4 ; ++i)
            {
                int y = a + dy[i] , x = b + dx[i];
                if(x >= 0 && y >= 0 && x < n && y < m && board[y][x] == 'O')
                {
                    board[y][x] = '.';
                    q.push({y,x});
                }
            }
        }
    }
    void solve(vector<vector<char>>& board) {
        m = board.size() , n = board[0].size();
        queue<PII> q;
        for(int i = 0 ; i < m ; ++i)
        {
            if(board[i][0] == 'O') bfs(board,i,0);
            if(board[i][n-1] == 'O') bfs(board,i,n-1);
        }
        for(int j = 0 ; j < n ; ++j)
        {
            if(board[0][j] == 'O') bfs(board,0,j);
            if(board[m-1][j] == 'O') bfs(board,m-1,j);
        }
        for(int i = 0 ; i < m ; ++i)
        {
            for(int j = 0 ; j < n ; ++j)
            {
                if(board[i][j] == 'O') board[i][j] = 'X';
                else if(board[i][j] == '.') board[i][j] = 'O';
            }
        }
    }
};